1. Field of the Invention
The present invention relates to a crossbar switch in a multi-processor system.
2. Description of the Related Art
In a multiprocessor system, a self-routing crossbar switch is often used to connect a plurality of processors with a plurality of memory modules. The processors are connected to the input ports and memory modules to the output ports. In vector processing computers, the processors are vector processing units that perform the same operation on multiple data streams. For example, an operation may consist of fetching a pair of operands from two arrays A and B present in the memory, adding the fetched pair and storing the result back into the memory in a third array C. To fully utilize the processing capability of the vector processing units (VPUs), it is necessary that the operands required to perform the operation are made available to the VPUs at a rate that is commensurate with their processing capability. Self-routing crossbar switches can be used to interconnect the VPUs with the memory modules so that if the VPUs access different output ports, all the VPU accesses to the memory can progress simultaneously. The self-routing crossbar switches can also be used to interconnect general purpose processing units to achieve very high system throughput. The self-routing crossbar switches also find applications in telephone exchanges where a number of subscribers have to be interconnected simultaneously. The ATM (Asynchronous Transfer Mode) switch is an example of a self-routing crossbar switch extensively used in the telecommunications field.
Consider a self-routing crossbar switch consisting of 2N ports, N processors are connected on one side and N memory modules to the other side to the ports of the self routing crossbar switch. If the N processors access the N memory modules, all the accesses can progress simultaneously. The bank conflict issue is ignored for a moment to simplify the discussion. If more than one processor attempts to access the same port at the same time, port conflict is said to occur. The input requests have to be serviced sequentially. If more requests arrive at a port when previous requests have not been serviced, the incoming requests have to be stored temporarily.
The requests are stored in a first-in first-out (FIFO) buffer, for example. In Mark J. Karol et al. "Input Versus Output Queueing on a Space-Division Packet Switch", IEEE Transaction on Communication, Vol. COM-35, No. 12, December 1987, there is disclosed a technology for reducing influence of port conflict by providing a FIFO buffer at an input or output side of the crossbar switch. In the prior art, if the port conflict occurs at the output side, the overall performance is improved by reducing influence of the port conflict for the input side.
However, in the prior art, it becomes necessary to arbitrate a plurality of requests which are causing port conflict and to supply them to the port in an appropriate order.
On the other hand, even in the case where no port conflict is occurring, it is possible to have a bank conflict as discussed below, which may potentially be a cause of degradation of performance. In the memory system, assuming a memory cycle is M, it is required to wait for the period M in order to access the same memory. Therefore, in the memory system directed to higher performance, interleaved P memory banks are provided so that each memory bank may be accessed in a period of M/P. However, even in such banked memory system, it is still required to wait for the period M (hereinafter referred to as "bank cycle") in order to sequentially access the same memory bank. Occurrence of access for the same memory bank within the bank cycle is referred to as the bank conflict.